package leetcode.code0316;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

//执行用时：1 ms, 在所有 Java 提交中击败了100.00%的用户
//
//内存消耗：38.5 MB, 在所有 Java 提交中击败了38.71%的用户
//
//通过测试用例：289 / 289
public class Solution implements IDebug {

	public String removeDuplicateLetters(String s) {
		char[] cs = s.toCharArray();// 原串字符数组
		int[] counts = new int[128];// 记录剩余的字符数量，不想 - 'a' , 闹眼睛
		for (char c : cs) {
			counts[c]++;
		}
		int len = s.length();
		char[] stack = new char[len];// 存放字符
		int p = 0;
		char cur = ' ';
		boolean[] has = new boolean[128];// 单调栈中是否出现该字符
		for (int i = 0; i < len; i++) {
			char c = cs[i];// 当前字符
			// while (栈中有字符 && 栈顶字符顺序大于小字符c && 栈里不存在小字符c && 后面还有栈顶字符) {栈顶字符不要了}
			while (p > 0 && (cur = stack[p - 1]) >= c && !has[c] && counts[cur] > 0) {
				p--;// 出栈
				has[cur] = false;// 栈顶字符不存在了
			}
			// 不存在就加入栈 潜台词，存在一个重复的字符，说明两者中间有个唯一大字符挡着，顺序不能变了
			if (!has[c]) {
				stack[p++] = c;// 入栈
				has[c] = true;// 标记字符出线
			}
			counts[c]--;// 处理完一个字符，剩余就少一个字符
		}
		return new String(stack, 0, p);// 栈中元素即所求
	}

	@Override
	public void debug1() {
		HelpDebug.compare("abc", this.removeDuplicateLetters("bcabc"));

	}

	@Override
	public void debug2() {
		HelpDebug.compare("acdb", this.removeDuplicateLetters("cbacdcbc"));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub
		HelpDebug.compare("abginsudeqwrcvzxtfhko",
				this.removeDuplicateLetters("cnazanfixhanbgbxuangnoxingbzngnsaudfbaerqwerbazcvzxcgasdatfhfdgkhobcabc"));

	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug3();
		so.debug2();
		so.debug1();
		so.debug4();

	}

}
